package com.lagou.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class TaskTwo {

  /**
   * 金矿
   */
  public static class GoldMine {

    /**
     * 金矿储量
     */
    private Integer reverses;

    /**
     * 需要工人数量
     */
    private Integer needWorkerNum;

    public GoldMine(Integer reverses, Integer needWorkerNum) {
      this.reverses = reverses;
      this.needWorkerNum = needWorkerNum;
    }

    public Integer getReverses() {
      return reverses;
    }

    public Integer getNeedWorkerNum() {
      return needWorkerNum;
    }
  }

  public static class State {

    private Integer value;
    private List<Integer> goldMineList = new ArrayList<Integer>();

    public State() {
      this.value = 0;
    }

    public State(Integer value, Integer goldMineNum) {
      this.value = value;
      goldMineList.add(goldMineNum);
    }

    public void setValueAndGoldNum(List<Integer> goldNumList, Integer value) {
      this.value = value;
      this.goldMineList = goldNumList;
    }

    public Integer getValue() {
      return value;
    }

    public List<Integer> getGoldMineList() {
      return goldMineList;
    }
  }

  /**
   * 动态规划选取金矿
   *
   * @param goldMines 金矿列表
   * @param n 金矿数量
   * @param w 工人数量
   */
  public static List<Integer> pickGoldMines(GoldMine[] goldMines, int n, int w) {
    State[][] states = new State[n][w + 1];
    // 初始化states
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < w + 1; ++j) {
        states[i][j] = new State();
      }
    }
    if (goldMines[0].needWorkerNum <= w) {
      states[0][goldMines[0].needWorkerNum] = new State(goldMines[0].getReverses(), 0);
    }
    // 动态规划，状态转移
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= w; ++j) {
        // 不挖第i个金矿
        if (states[i - 1][j].getValue() > 0) {
          states[i][j] = states[i - 1][j];
        }
      }
      // 选择第i个金矿
      for (int j = 0; j <= w - goldMines[i].getNeedWorkerNum(); ++j) {
        if (states[i - 1][j].getValue() > 0) {
          int v = states[i - 1][j].getValue() + goldMines[i].getReverses();
          if (v > states[i][j + goldMines[i].getNeedWorkerNum()].getValue()) {
            List<Integer> goldMineList = new ArrayList<Integer>();
            goldMineList.addAll(states[i - 1][j].goldMineList);
            goldMineList.add(i);
            states[i][j + goldMines[i].getNeedWorkerNum()].setValueAndGoldNum(goldMineList, v);
          }
        }
      }
    }
    // 找出最大值
    State maxValue = new State();
    for (int j = 0; j <= w; ++j) {
      if (states[n - 1][j].getValue() > maxValue.getValue()) {
        maxValue = states[n - 1][j];
      }
    }
    return maxValue.getGoldMineList();
  }

  private static final int maxWorkerNum = 10;

  private static GoldMine[] goldMines = new GoldMine[]{
      new GoldMine(500, 5),
      new GoldMine(200, 3),
      new GoldMine(300, 2),
      new GoldMine(200, 4),
      new GoldMine(400, 4)
  };

  public static void main(String[] args) {
    List<Integer> goldMineNumList = pickGoldMines(goldMines, 5, maxWorkerNum);
    System.out.println(Arrays.toString(goldMineNumList.toArray()));
  }

}
